#include<stdio.h>
#include"lkstack.h"



/*2.
    利用栈,计算从键盘输入的表达式的值,表达式以字符串的形式输入并且只包含基本的 + - * / %
        扩展:实现带小数点的运算
            实现带括号的运算
    int  expressionValue(char *str)
    {
    }
    两种思路
    1:直接计算结果
        //初始化两个栈(一个存放操作数,另一个存放运算符)
        //遍历表达式,解析出数字和符号
        while(*str)
        {
            //解析出操作数,就直接入栈
            //解析出运算符,就分情况讨论(最终目的也是入栈)
            while(1)
            {
                if(当前运算符栈为空 || 当前运算符的优先级比栈顶运算符的优先级高 || 如果栈顶运算符是（，运算符入栈 || 如果栈顶运算符是）)
                {
                    if(运算符是）)
                    {
                        // ）不入栈
                        // 取出栈顶运算符和两个操作数（或者更多，做运算）
                        // 做运算,把结果存放到操作数栈
                        // 并且将此时的栈顶运算符）取出，此时的栈顶运算符是（下面的运算符
                    }
                    //运算符直接入栈
                    break;
                }
                //如果运算符是（，则直接入栈
                //如果运算符是），者
                else   (把当前栈顶运算符给消耗掉)
                {
                    //取出栈顶运算符和两个操作数
                    //做运算符,把结果存放到操作数栈
                }
            }
            str++;
        }
   */

  

int getPrecedence(char op)
{
    switch (op)
    {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
        case '%':
            return 2;
    }
    
}


int  expressionValue(char *str)
{
    //初始化两个栈(一个存放操作数,另一个存放运算符)
    LKstack *q1 = InitStack();//存放操作数
    LKstack *q2 = InitStack();//存放运算符
    //遍历表达式,解析出数字和符号
    while(*str)
    {
        int i = 0;
        //解析出操作数,就直接入栈
        while(*str >='0' && *str <='9')
        {
            i = i*10 + (*str-'0'); 
            str++;
        }
        //入栈
        Push(q1,i);
        //整个表达式遍历完成   
        if(*str =='\0')
        {
            break;
        }
        //解析出运算符,就分情况讨论(最终目的也是入栈)
        while(1)
        {
            //当前运算符栈为空 || 当前运算符的优先级比栈顶运算符的优先级高 || 如果栈顶运算符是（，运算符入栈 || 如果栈顶运算符是）
            if(StackIsEmpty(q2) || getPrecedence(str[i])>getPrecedence(q2->first) || str[i] == '(' || q2->first == ')')
            {
                //运算符是）
                if(q2->first == ')')// ）不入栈
                {
                    int v1;
                    int v2;
                    int v3;
                    //取出栈顶，保存在v1，在去除当前栈顶
                    GetTop(q1,&v1);
                    Pop(q1);
                    //取出当前栈顶，保存在v2，在去除当前栈顶
                    GetTop(q1,&v2);
                    Pop(q1);
                    //去除q2运算符，放在v3
                    GetTop(q2,&v3);
                    Pop(q2);
                    //v = v1 v3 v2;
                    Push(q1,Calculation(v2,v3,v1));
                    // 取出栈顶运算符和两个操作数（或者更多，做运算）
                    // 做运算,把结果存放到操作数栈
                    // 并且将此时的栈顶运算符）取出，此时的栈顶运算符是（下面的运算符
                }
                else
                {
                    //运算符直接入栈
                    Push(q2,*str);
                    break;
                }
                
            }
            
            else   //(把当前栈顶运算符给消耗掉)
            {
                //取出栈顶运算符和两个操作数
                //做运算符,把结果存放到操作数栈
                int v1;
                int v2;
                int v3;
                //取出栈顶，保存在v1，在去除当前栈顶
                GetTop(q1,&v1);
                Pop(q1);
                //取出当前栈顶，保存在v2，在去除当前栈顶
                GetTop(q1,&v2);
                Pop(q1);
                //去除q2运算符，放在v3
                GetTop(q2,&v3);
                Pop(q2);
                //v = v1 v3 v2;
                Push(q1,Calculation(v2,v3,v1));
        }
            
        }
        str++;
    }
}





void Conversion(int num,int x)
{
    //先生成一个链表队列
    LKstack *q = InitStack();

    //开始计算
    //循环
    while(num)
    {
        //取x的余数，将其保存到栈中，佳能一个属插入栈中
        Push(q,num%x);
        //整数部分还要用，当成新的num
        num = num/x;
    }
    //出栈
    printf("转换后的数字：");
    while(!StackIsEmpty (q))//判断栈是否为空
    {
        //现在出来的是单独一个节点，不仅仅包含data,要利用函数Gettop的到data
        int v;
        GetTop(q,&v);
        if(v<=9)
        {
            printf("%c",v+'0');
        }else
        {
            //10--->A
            printf("%c",v+55);
        }
        Pop(q);
    }
    printf("\n");
    //消除栈
    DestoryStack(q);

}

int main()
{
    Conversion(1023,2);
    return 0;
}


/*
int main()
{
    //初始化一个栈,栈里面没有任何用户数据
    LKstack * s = InitStack();
    printf("栈是否为空:%d\n", StackIsEmpty(s) );
    printf("栈的长度:%d\n", StackSize(s) );


    Elemtype a = 0; //可用的空间
    if( GetTop(s,&a) )
    {
        printf("获取成功:%d\n",a);
    }else
    {
        printf("获取失败!\n");
    }

    Push(s,1);
    Push(s,2);
    Push(s,3);
    Push(s,4);
    Push(s,5);

    printf("==============================\n");

    printf("栈是否为空:%d\n", StackIsEmpty(s) );
    printf("栈的长度:%d\n", StackSize(s) );
    if( GetTop(s,&a) )
    {
        printf("获取成功:%d\n",a);
    }else
    {
        printf("获取失败!\n");
    }

    Pop(s);
    Pop(s);

    printf("==============================\n");

    printf("栈是否为空:%d\n", StackIsEmpty(s) );
    printf("栈的长度:%d\n", StackSize(s) );
    if( GetTop(s,&a) )
    {
        printf("获取成功:%d\n",a);
    }else
    {
        printf("获取失败!\n");
    }

    printf("==============================\n");
    while( !StackIsEmpty(s))
    {
        GetTop(s,&a);
        printf("value = %d\n",a);

        Pop(s);
    }


    //销毁
    DestoryStack(s);

    return 0;
}
    */